import sys
from Queue import Queue
from Queue import PriorityQueue
import ALGhelper

def MainFunction(filename):

    data = ALGhelper.ReadFile(filename)

    data2 = ALGhelper.ChangeProblem(data, 2.0/3.0)

    qedgelist = ALGhelper.GetEdgeList(data2)

    faclist = ALGhelper.InitFacItem(data2)

    qfaclist = ALGhelper.InitQFacItem(data2)


    current_time = 0.0
    alpha = []
    for i in range(0, data2.cnum):
        alpha.append(-1)

    while not (qedgelist.empty() or qfaclist.empty()):

        etop = qedgelist.get()
        ftop = qfaclist.get()

        if (etop[0] < ftop[0]):     #an edge goes tight first
            qfaclist.put(ftop)
            current_time = etop[0]
            i = etop[1]     #fid    = -1 mean p
            j = etop[2]     #cid
            if i != -1:     #not p
                if faclist[i].vol > ALGhelper.mymin:  #fac i not filled yet
                    faclist[i].updatedata(current_time, 1)
                    qfaclist.put((ALGhelper.GetExpectFillTime(faclist[i]), ALGhelper.QFacItem(i, faclist[i].updateid))) 
                else:                                   #fac i filled yet
                    alpha[j] = current_time
                    for ii in range(0, data2.fnum):
                        if current_time > data2.c[ii][j]:     #update fac ii
                            faclist[ii].updatedata(current_time, -1)
                            qfaclist.put((ALGhelper.GetExpectFillTime(faclist[ii]),  ALGhelper.QFacItem(ii, faclist[ii].updateid)))     
            else:           #p
                alpha[j] = current_time
                for ii in range(0, data2.fnum):
                    if current_time > data2.c[ii][j]:     #update fac ii
                        faclist[ii].updatedata(current_time, -1)
                        qfaclist.put((ALGhelper.GetExpectFillTime(faclist[ii]),  ALGhelper.QFacItem(ii, faclist[ii].updateid))) 
             
        else:                       #a fac goes tight first
            qedgelist.put(etop)
            current_time = ftop[0]
            i = ftop[1].fid
            faclist[i].updatedata(current_time, 0)
            for j in range(0, data2.cnum):
                if alpha[j] < 0 and current_time > data2.c[i][j]:
                    alpha[j] = current_time
                    for ii in range(0, data2.fnum):
                        if current_time > data2.c[ii][j]:     #update fac ii
                            faclist[ii].updatedata(current_time, -1)
                            qfaclist.put((ALGhelper.GetExpectFillTime(faclist[ii]),  ALGhelper.QFacItem(ii, faclist[ii].updateid))) 

        while not qfaclist.empty():  #filter the out-date data
            ftop = qfaclist.get()
            if ftop[1].updateid == faclist[ftop[1].fid].updateid:
                qfaclist.put(ftop)
                break

        while not qedgelist.empty(): #filter the out-date data
            etop = qedgelist.get()
            if alpha[etop[2]] < 0:
                qedgelist.put(etop)
                break

    #print alpha

    ff = []
    for i in range(0, data2.fnum):
        ff.append(data2.f[i])

    for i in range(0, data2.fnum):
        for j in range(0, data2.cnum):
            if (alpha[j] > data2.c[i][j]):
                ff[i] -= alpha[j] - data2.c[i][j]

    #print ff

    Fopen = ALGhelper.GetSetFopen(data2, faclist, alpha)
    print Fopen
    Fopen.append(data2.fnum)

    data2.fnum+=1
    data2.f.append(0)
    data2.c.append(data2.p)

    client_fac = []
    for j in range(0, data2.cnum):
        client_fac.append(0)

    ALGhelper.AnsUpdate(data2, Fopen, client_fac)

    opened_fac = []
    for i in range(0, data2.fnum):
        opened_fac.append(False)
    for i in Fopen:
        opened_fac[i] = True

    while True:
        r = -1
        add_fac = -1
        for i in range(0, data2.fnum):
            if not opened_fac[i]:
                tmp = ALGhelper.Gain(data2, client_fac, i) * 1.0 / data2.f[i]
                if tmp > r:
                    r = tmp
                    add_fac = i
        if r > ALGhelper.mymin:
            Fopen.append(add_fac)
            opened_fac[add_fac] = True
            ALGhelper.AnsUpdateOne(data2, add_fac, client_fac)
        else:
            break

    #print Fopen


    opened_time = []
    for i in range(0, data.fnum):
        opened_time.append(0)
    ans = 0
    for j in range(0, data.cnum):
        if client_fac[j] == data.fnum:
            print "Client %d choose penality"%j
            ans += data.p[j]
        else:
            #print "Client %d choose Fac %d"%(j,client_fac[j])
            ans += data.c[client_fac[j]][j]
            opened_time[client_fac[j]]+=1

    for i in range(0, data.fnum):
        if opened_time[i] > 0:
            tm = (opened_time[i] - 1) / data.u[i] + 1
            #print "Fac %d opened %d time(s)"%(i,tm)
            ans += data.f[i]*tm

    return ans

        
            
    








